package Lee_code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @author blh
 * @date 2024年11月18日 16:47
 * 串联所有单词的子串
 */
public class Lee_30_1118 {
    int subLen;
    int wordLen;
    HashMap<String, Integer> seen;

    public List<Integer> findSubstring(String s, String[] words) {
        // 構建hash表
        seen = new HashMap<>();
        // 初始化哈希映射
        for (String word : words) {
            seen.put(word, seen.getOrDefault(word, 0) + 1);
        }
        // 单词长度
        wordLen = words[0].length();
        // 子串长
        subLen = wordLen * words.length;
        // 返回结果
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i <= s.length() - subLen; ) {
            if (beStarter(i, words, s)) {
                res.add(i);
            }
            i++;
        }
        return res;
    }

    private boolean beStarter(int index, String[] words, String s) {
        HashMap<String, Integer> tempSeen = new HashMap(this.seen);
        for (int i = index; i < index + subLen; i += wordLen) {
            if (tempSeen.getOrDefault((s.substring(i, i + wordLen)), 0) > 0) {
                tempSeen.put(s.substring(i, i + wordLen), tempSeen.get(s.substring(i, i + wordLen)) - 1);
            } else {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        Lee_30_1118 method = new Lee_30_1118();
        // [8]
        System.out.println(method.findSubstring("wordgoodgoodgoodbestword", new String[]{"word", "good", "best", "good"}));
    }
}
